﻿#light

(*Paly with recursive functions in f#

let rec sieveOfEra xs =
    match xs with
        | [] -> [] // if empty list passed in, quit
        | h::t ->
            h::(sieveOfEra (List.filter (fun x -> x % h <> 0) t))

let rec fac n = 
    match n with 
        | 0 -> 1 
        | _ -> n * fac (n-1)
 
let rec factorial n = if n=0 then 1 else n * factorial (n-1)

//n can't be less then zero    
let rec fib n =
    match n with
        | 0 -> 0
        | 1 -> 1
        | _ -> fib(n - 1) + fib(n - 2)
  
  
let rec fib2 = function
    | x when x < 0 -> failwith "value cannot be less than 0."
    | 0 | 1 as x -> x
    | x -> fib2(x - 1) + fib2(x - 2) 
END*)

    
//Tsts frrom the papper


//flip flip
type Elem = int

type Tree = Empty | Branch of Elem*Tree*Tree

let testTree = Branch(1, Branch(2,Empty,Empty), Branch(3,Empty,Empty))

let rec flip (t:Tree) = 
    match t with
    | Empty -> Empty
    | Branch(l, a, b) -> Branch(l, flip(b), flip(a))
    
let rec insert (x:int) (t:Tree) :Tree = 
    match t with
        | Empty -> Branch(x, Empty, Empty)
        | Branch(y, a, b) when x < y -> Branch(y, (insert x a), b)
        | Branch(y, a, b) when y < x -> Branch(y, a, (insert x b))
        
let rec insertList (xs:int list) (t:Tree) :Tree= 
    match xs with
        | [] -> t
        | x::xs -> insertList xs (insert x t)

let genTree n = insertList [(-n/2)..0] (insertList [1..(n/2)] Empty)

let rec printTree (t:Tree) = 
    match t with
        | Empty -> printf "Empty"
        | Branch(x, a, b) -> printf "%d" x
                             printTree a
                             printf "\n"
                             printTree b
        
//sum (map spuare (upto 1 n))
let square x = x*x

//n<1861
let paperTest (n:int) :int = List.sum (List.map square [1..n])

let rec h a m n = 
    match m > n with
        | true -> a
        | _ -> h (a+square m) (m+1) n

let DpaperTest n = h 0 1 n


//append append

let rec myAppend xs ys = 
    match xs with
        | [] -> ys
        | (head::tail) -> head::(myAppend tail ys)

let paperTest2 xs ys zs = List.append (List.append xs ys) zs

let paperTest2int (n : int) = paperTest2 [1..n] [1..n] [1..n]

let rec h1 ys zs = 
    match ys with
        | [] -> []
        | (y::ys) -> y :: (h1 ys zs)

let rec h0 xs ys zs = 
    match xs with
        | [] -> h1 ys zs
        | (x::xs) -> x :: (h0 xs ys zs)

let DpaperTest2 xs ys zs = h0 xs ys zs

let DpaperTest2int n = DpaperTest2 [1..n] [1..n] [1..n]


//Preformanstests on the tests
let rec TestInt timesTested input testFunction deforestedTestFunction = 
    match timesTested with
        | 0 -> 0
        | _ -> let s1 = System.DateTime.UtcNow
               let f = (testFunction input)
               printfn "function Execution time: %d" (System.DateTime.UtcNow - s1).Milliseconds
    
               let s2 = System.DateTime.UtcNow
               let d = (deforestedTestFunction input)
               printfn "Deforested Execution time: %d" (System.DateTime.UtcNow - s2).Milliseconds
               
               printfn "%b\n\n" (f.Equals d)
               TestInt (timesTested-1) input testFunction deforestedTestFunction

let rec intMemTest (f:int->int list) (input:int) (inc:int) :int = 
    match input with
        | -1 -> -1
        | _ -> printfn "input: %d" input
               f input
               intMemTest f (input+inc) inc


[<EntryPoint>]
let Main args = 
    
    //printf "Deforested sumSquaredList %d" (DpaperTest 1000000000)
    
    //intMemTest DpaperTest2int 100 50
    
    //let r = TestInt 20 1860 paperTest DpaperTest
    
    printTree (genTree 4)
    
    (*printfn ""
    print_any (flip testTree)
    printfn ""
    print_any (flip (flip testTree))
    
    printfn "%b" (testTree.Equals (flip (flip testTree)))*)
    
    printfn "\nEND"
    0

(*printfn "fac = %d" (fac 20)
printfn "factorial = %d" (factorial 20)
printfn "END"
System.Console.ReadKey |> ignore*)